package dp;

import java.util.List;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *
 * 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，
 * 如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 *
 * author: Mr.Du
 * Date: 2023/4/14
 * Time: 20:57
 */
public class MinimumTotal {


    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];

        // 初始化 dp 数组的最后一行
        for (int j = 0; j < n; j++) {
            dp[n-1][j] = triangle.get(n-1).get(j);
        }

        // 从倒数第二行开始逐层向上计算
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                // 状态转移方程：dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
                dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }

        return dp[0][0]; // 最终结果保存在 dp[0][0] 中
    }

}
